package od_2025A.one;


import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * todo 哈夫曼树
 * https://blog.csdn.net/qq_45776114/article/details/145905709
 * 题目核心：
 * 1、构建哈夫曼树 （优先级队列）
 * 2、中序遍历树结构
 */
public class Test12 {

    static class Node {
        // 当前节点值
        int value;

        // 子节点数，包含当前节点
        int num;

        // 左节点
        Node left;

        // 右节点
        Node right;

        public Node(int value, int num) {
            this.value = value;
            this.num = num;
        }
    }

    public static class CompareNode implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            if (o1.value == o2.value) {
                return Integer.compare(o1.num, o2.num);
            }
            return Integer.compare(o1.value, o2.value);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int count = Integer.parseInt(scanner.nextLine());
        String[] strArray = scanner.nextLine().split(" ");
        scanner.close();

        // 构建优先级队列，利用优先级队列构建哈夫曼树
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(new CompareNode());
        for (String str : strArray) {
            int value = Integer.parseInt(str);
            Node node = new Node(value, 1);
            priorityQueue.offer(node);
        }
        while (priorityQueue.size() > 1) {
            Node left = priorityQueue.poll();
            Node right = priorityQueue.poll();
            // 构建父节点
            Node parent = new Node(left.value + right.value, left.num + right.num + 1);
            parent.right = right;
            parent.left = left;
            priorityQueue.offer(parent);
        }

        Node root = priorityQueue.poll();
        dfs(root);
    }

    private static void dfs(Node root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        System.out.print(root.value + " ");
        dfs(root.right);
    }
}
